package com.algorithm;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigDecimal;
import java.math.MathContext;
import java.util.HashMap;
import java.util.Map;

/**
 * 获取期望数字的的个数
 * 问题描述如下:
 *      统计一下 aaa ⋯ aaa (n个a表示的n位数) × b 的结果里面有多少个数字d，a,b,d均为一位数。
 * 样例解释：
 *      3333333333*3=9999999999，里面有10个9。
 * <p>
 * Input
 *      多组测试数据。
 *      第一行有一个整数T，表示测试数据的数目。(1≤T≤5000)
 *      接下来有T行，每一行表示一组测试数据，有4个整数a，b，d，n。 (1≤a,b≤9，0≤d≤9，1≤n≤10^9)
 * Output
 *      对于每一组数据，输出一个整数占一行，表示答案。
 * Input示例
 *      2
 *      3 3 9 10
 *      3 3 0 10
 * Output示例
 *      10
 *      0
 * <p>
 * 解题思路:
 * 1、解析控制台输入参数
 * 2、通过等比数列前n项和公式计算n位a的值。
 * 3、计算n位a 乘以 b的值,要注意选择合适的范围的数据类型
 * 4、将计算结果转成字符串,继而获取字符数组,求数组中元素相同hash值的元素个数并以hashMap记录
 * Created by houjinxin on 16/5/27.
 */
public class GetExceptNoTimes {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out), 1 << 16);
        String input = reader.readLine();
        int lineNumber = Integer.parseInt(input);
        while (lineNumber > 0) {
            input = reader.readLine();
            writer.write(getExceptNoTimes(input.split(" ")) + "\r\n");
            lineNumber--;
        }
        writer.flush();
    }

    public static int getExceptNoTimes(String[] params) {
        if (params.length != 4) {
            throw new IllegalArgumentException("参数个数不等于4,重新输入");
        }
        String aStr = params[0];
        String bStr = params[1];
        String dStr = params[2];
        String nStr = params[3];
        //求n个a表示n位数的值
        BigDecimal exceptNumber = getSumOfTheGeometricProgression(BigDecimal.valueOf(Long.parseLong(aStr)), Integer.parseInt(nStr)).multiply(BigDecimal.valueOf(Long.parseLong(bStr)));
        Map<Character, Integer> map = getCharacterIntegerMap(String.valueOf(exceptNumber));
        Integer times = map.get(dStr.charAt(0));
        return times != null ? times : 0;
    }

    /**
     * 大数运算
     * 10^n -1 / firstItem
     * @param firstItem
     * @param n
     * @return
     */
    private static BigDecimal getSumOfTheGeometricProgression(BigDecimal firstItem, int n) {
        BigDecimal base;
        if (n > 999999999) {
            base = BigDecimal.TEN.pow(999999999).multiply(BigDecimal.TEN.pow(n - 999999999)) ;
        }
        else {
            base = BigDecimal.TEN.pow(n);
        }
        return  base.subtract(BigDecimal.ONE).divide(firstItem, 0);
    }

    public static Map<Character, Integer> getCharacterIntegerMap(String perfectString) {
        char[] chars = perfectString.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (char e : chars) {
            Integer eTimes = map.get(e);
            if (eTimes == null) {
                map.put(e, 1);
            } else {
                map.put(e, ++eTimes);
            }
        }
        return map;
    }
}
